{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Construct Binary Tree from String"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #tree #depth-first-search #string #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树 #深度优先搜索 #字符串 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: str2tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #从字符串生成二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你需要用一个包括括号和整数的字符串构建一棵二叉树。</p>\n",
    "\n",
    "<p>输入的字符串代表一棵二叉树。它包括整数和随后的 0 、1 或 2 对括号。整数代表根的值，一对括号内表示同样结构的子树。</p>\n",
    "\n",
    "<p>若存在子结点，则从<strong>左子结点</strong>开始构建。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "<img alt=\"\" src=\"https://assets.leetcode.com/uploads/2020/09/02/butree.jpg\" style=\"height: 322px; width: 382px;\" />\n",
    "<pre>\n",
    "<strong>输入：</strong> s = \"4(2(3)(1))(6(5))\"\n",
    "<strong>输出：</strong> [4,2,6,3,1,5]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> s = \"4(2(3)(1))(6(5)(7))\"\n",
    "<strong>输出：</strong> [4,2,6,3,1,5,7]\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3:</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong> s = \"-4(2(3)(1))(6(5)(7))\"\n",
    "<strong>输出： </strong>[-4,2,6,3,1,5,7]\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0 &lt;= s.length &lt;= 3 * 10<sup>4</sup></code></li>\n",
    "\t<li>输入字符串中只包含&nbsp;<code>'('</code>, <code>')'</code>, <code>'-'</code>&nbsp;和&nbsp;<code>'0'</code> ~ <code>'9'</code>&nbsp;</li>\n",
    "\t<li>空树由&nbsp;<code>\"\"</code>&nbsp;而非<code>\"()\"</code>表示。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [construct-binary-tree-from-string](https://leetcode.cn/problems/construct-binary-tree-from-string/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [construct-binary-tree-from-string](https://leetcode.cn/problems/construct-binary-tree-from-string/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"4(2(3)(1))(6(5))\"', '\"4(2(3)(1))(6(5)(7))\"', '\"-4(2(3)(1))(6(5)(7))\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if s == \"\":\n",
    "            return None\n",
    "\n",
    "        stk = []\n",
    "        i = 0\n",
    "        while i < len(s):\n",
    "            if s[i] == '(':\n",
    "                i += 1\n",
    "                continue \n",
    "\n",
    "            if s[i] == ')':\n",
    "                stk.pop()\n",
    "                i += 1\n",
    "                continue \n",
    "\n",
    "            num = 0\n",
    "            sign = 1\n",
    "            if s[i] == '-':\n",
    "                sign = -1\n",
    "                i += 1\n",
    "            \n",
    "            j = i\n",
    "            while j < len(s) and ord('0') <= ord(s[j]) <= ord('9'):\n",
    "                num = num * 10 + int(s[j])\n",
    "                j += 1\n",
    "            i = j - 1\n",
    "            num = sign * num \n",
    "            node = TreeNode(num)\n",
    "\n",
    "            if stk:\n",
    "                pat = stk[-1]\n",
    "                if pat.left is None:\n",
    "                    pat.left = node\n",
    "                elif pat.right is None:\n",
    "                    pat.right = node\n",
    "            stk.append(node)\n",
    "\n",
    "            i += 1\n",
    "\n",
    "        return stk.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        l = s.find('(')\n",
    "        # print(s, l)\n",
    "        \n",
    "        if l == -1:\n",
    "            return TreeNode(val=int(s)) if s != '' else None\n",
    "        \n",
    "        \n",
    "        r = l + 1\n",
    "        cnt = 1\n",
    "        while cnt != 0:\n",
    "            if s[r] == '(':\n",
    "                cnt += 1\n",
    "            elif s[r] == ')':\n",
    "                cnt -= 1\n",
    "            r += 1\n",
    "        \n",
    "        # print(l, r, s[:l], s[l+1:r-1], s[r+1:-1])\n",
    "        return TreeNode(val=int(s[:l]), \n",
    "                        left=self.str2tree(s[l+1:r-1]), \n",
    "                        right=self.str2tree(s[r+1:-1]))\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        n=len(s)\n",
    "        if n==0:return None\n",
    "        isf=False\n",
    "        cur=0\n",
    "        if s[0]=='-':\n",
    "            isf=True\n",
    "            cur=1\n",
    "        k=0\n",
    "        while cur <n and s[cur]!='(':\n",
    "            k*=10\n",
    "            k+=int(s[cur])\n",
    "            cur+=1\n",
    "        if isf:k*=-1\n",
    "        r=TreeNode(k)\n",
    "        if cur==n:return r\n",
    "        ls=cur\n",
    "        t=0\n",
    "        while cur<n:\n",
    "            if s[cur]==')':\n",
    "                t-=1\n",
    "            elif s[cur]=='(':\n",
    "                t+=1\n",
    "            cur+=1\n",
    "            if t==0:break\n",
    "        r.left=self.str2tree(s[ls+1:cur-1])\n",
    "        if cur==n:return r\n",
    "        r.right=self.str2tree(s[cur+1:-1])\n",
    "        return r\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        start=0\n",
    "        if s[0] == '-':\n",
    "            sign = -1\n",
    "            start+=1\n",
    "        else:\n",
    "            sign = 1\n",
    "\n",
    "        v = 0\n",
    "        left1 = 0\n",
    "        for i in range(start,len(s)):\n",
    "            if s[i] != '(':\n",
    "                v = v * 10 + int(s[i])\n",
    "            else:\n",
    "                left1 = i\n",
    "                break\n",
    "\n",
    "        cnt = 0\n",
    "        right1 = 0\n",
    "        for i in range(left1, len(s)):\n",
    "            if s[i] == '(':\n",
    "                cnt += 1\n",
    "            elif s[i] == ')':\n",
    "                cnt -= 1\n",
    "            if cnt == 0:\n",
    "                right1 = i\n",
    "                break\n",
    "\n",
    "        cnt = 0\n",
    "        left2 = right1 + 1\n",
    "        right2 = 0\n",
    "        for i in range(left2, len(s)):\n",
    "            if s[i] == '(':\n",
    "                cnt += 1\n",
    "            elif s[i] == ')':\n",
    "                cnt -= 1\n",
    "            if cnt == 0:\n",
    "                right2 = i\n",
    "                break\n",
    "        return TreeNode(v*sign, self.str2tree(s[left1 + 1:right1]), self.str2tree(s[left2 + 1:right2]))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        # time complexity: O(NlogN) (平衡树) - O(N^2) (非平衡树/链表)\n",
    "        # space complexity:  O(logN) - O(N)\n",
    "\n",
    "        \"\"\"\n",
    "        找根节点值:\n",
    "            使用index找到第一个\"(\"的位置，s[:index]就是根节点的值。\n",
    "            使用这个值创建一个新的根节点root。\n",
    "        查找子树字符串: \n",
    "            使用一个循环从index开始遍历字符串s。\n",
    "            使用count来追踪打开和关闭的括号，\"(\"会增加count，\")\"会减少count。\n",
    "            当count变为0时，说明找到了一个完整的子树表达式。\n",
    "            如果start等于index，找到的是左子树，使用s[start + 1: i]递归调用str2tree方法并将返回值设为root的左子节点。\n",
    "            如果start不等于index，找到的是右子树，使用s[start + 1: i]递归调用str2tree方法并将返回值设为root的右子节点。\n",
    "\n",
    "        \"\"\"\n",
    "\n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return None\n",
    "        \n",
    "        if \"(\" not in s:\n",
    "            return TreeNode(int(s))\n",
    "\n",
    "        index = s.index(\"(\")\n",
    "        root = TreeNode(int(s[:index]))\n",
    "        start = index\n",
    "        count = 0\n",
    "        for i in range(index, n):\n",
    "            if s[i] == \"(\": \n",
    "                count += 1\n",
    "            elif s[i] == \")\":\n",
    "                count -= 1\n",
    "            \n",
    "            if count == 0: \n",
    "                if start == index:\n",
    "                    root.left = self.str2tree(s[start + 1: i])\n",
    "                    start = i + 1\n",
    "                elif start != index:\n",
    "                    root.right = self.str2tree(s[start + 1: i])\n",
    "        \n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]: \n",
    "        # time complexity: O(NlogN) (平衡树) - O(N^2) (非平衡树/链表)\n",
    "        # space complexity:  O(logN) - O(N)\n",
    "\n",
    "        \"\"\"\n",
    "        找根节点值:\n",
    "            使用index找到第一个\"(\"的位置，s[:index]就是根节点的值。\n",
    "            使用这个值创建一个新的根节点root。\n",
    "        查找子树字符串: \n",
    "            使用一个循环从index开始遍历字符串s。\n",
    "            使用count来追踪打开和关闭的括号，\"(\"会增加count，\")\"会减少count。\n",
    "            当count变为0时，说明找到了一个完整的子树表达式。\n",
    "            如果start等于index，找到的是左子树，使用s[start + 1: i]递归调用str2tree方法并将返回值设为root的左子节点。\n",
    "            如果start不等于index，找到的是右子树，使用s[start + 1: i]递归调用str2tree方法并将返回值设为root的右子节点。\n",
    "\n",
    "        \"\"\"     \n",
    "        n = len(s)\n",
    "        if n == 0:\n",
    "            return None\n",
    "        \n",
    "        if \"(\" not in s:\n",
    "            return TreeNode(int(s))\n",
    "\n",
    "        index = s.find(\"(\")\n",
    "\n",
    "        root = TreeNode(int(s[:index]))\n",
    "\n",
    "        count = 0\n",
    "        start = index\n",
    "        for i in range(index, n):\n",
    "            if s[i] == \"(\":\n",
    "                count += 1\n",
    "            \n",
    "            if s[i] == \")\":\n",
    "                count -= 1\n",
    "            \n",
    "            if count == 0:\n",
    "                if start == index:\n",
    "                    root.left = self.str2tree(s[start + 1: i])\n",
    "                    start = i + 1\n",
    "                else:\n",
    "                    root.right = self.str2tree(s[start + 1: i])\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        i = s.find('(')\n",
    "        if i == -1:\n",
    "            i = len(s)\n",
    "        root = TreeNode(int(s[:i]))\n",
    "        if len(s) == i:\n",
    "            return root\n",
    "        cnt = 1\n",
    "        j = i + 1\n",
    "        while j < len(s) and cnt > 0:\n",
    "            if s[j] == '(':\n",
    "                cnt += 1\n",
    "            elif s[j] == ')':\n",
    "                cnt -= 1\n",
    "            j += 1\n",
    "        #print(s,s[2:i - 1],s[i + 1:-1])\n",
    "        root.left = self.str2tree(s[i + 1:j - 1])\n",
    "        root.right = self.str2tree(s[j + 1:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if len(s)==0:\n",
    "            return None\n",
    "        if '(' not in s:\n",
    "            return TreeNode(int(s))\n",
    "        pos=s.index('(')\n",
    "        root=TreeNode(int(s[0:pos]))\n",
    "        start=pos\n",
    "        cnt=0\n",
    "        for i in range (pos,len(s)):\n",
    "            if s[i]=='(': cnt+=1\n",
    "            if s[i]==')': cnt-=1\n",
    "            if cnt==0 and start==pos:\n",
    "                root.left=self.str2tree(s[start+1:i])\n",
    "                start=i+1\n",
    "            elif cnt==0 and start!=pos:\n",
    "                root.right=self.str2tree(s[start+1:i])\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        n = len(s)\n",
    "        def dfs(s, index):\n",
    "            if index >= n:\n",
    "                return None, n + 1\n",
    "            neg = False\n",
    "            if s[index] == '-':\n",
    "                index += 1\n",
    "                neg = True\n",
    "            num = 0\n",
    "            while index < n and s[index].isdigit():\n",
    "                num *= 10\n",
    "                num += int(s[index])\n",
    "                index += 1\n",
    "            node = TreeNode(-num if neg else num)\n",
    "            if index < n and s[index] == '(':\n",
    "                left, nex = dfs(s, index + 1)\n",
    "                node.left = left\n",
    "                index = nex\n",
    "            if index < n and s[index] == '(':\n",
    "                right, nex = dfs(s, index + 1)\n",
    "                node.right = right\n",
    "                index = nex\n",
    "            return node, index + 1\n",
    "        \n",
    "        ans, _ = dfs(s, 0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        print(s)\n",
    "        i = s.find('(')\n",
    "        if i == -1:\n",
    "            i = len(s)\n",
    "        root = TreeNode(int(s[:i]))\n",
    "        if len(s) == i:\n",
    "            return root\n",
    "        cnt = 1\n",
    "        j = i + 1\n",
    "        while j < len(s) and cnt > 0:\n",
    "            if s[j] == '(':\n",
    "                cnt += 1\n",
    "            elif s[j] == ')':\n",
    "                cnt -= 1\n",
    "            j += 1\n",
    "        #print(s,s[2:i - 1],s[i + 1:-1])\n",
    "        root.left = self.str2tree(s[i + 1:j - 1])\n",
    "        root.right = self.str2tree(s[j + 1:-1])\n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        n = len(s)\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return i, None\n",
    "            \n",
    "            # 获取根节点的值\n",
    "            j = i\n",
    "            while j < n:\n",
    "                if s[j] in ('(', ')'):\n",
    "                    break\n",
    "                j += 1\n",
    "\n",
    "            # 创建根节点\n",
    "            root = TreeNode(val=int(s[i:j]))\n",
    "            i = j\n",
    "\n",
    "            # 判断是否有子节点\n",
    "            if i == n or s[i] == ')':\n",
    "                return i + 1, root \n",
    "            \n",
    "            i, left = dfs(i+1)\n",
    "            root.left = left\n",
    "\n",
    "            # 判断是否有右子节点\n",
    "            if i >= n or s[i] != '(':\n",
    "                return i+1, root\n",
    "            \n",
    "            i, right = dfs(i+1)\n",
    "            root.right = right\n",
    "\n",
    "            return i + 1, root\n",
    "\n",
    "\n",
    "        return dfs(0)[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        # 用栈模拟递归建树过程\n",
    "        stk = []\n",
    "        i = 0\n",
    "        while i<len(s):\n",
    "            if s[i] == \"(\":\n",
    "                i += 1\n",
    "                continue\n",
    "            if s[i] == \")\":\n",
    "                stk.pop()\n",
    "                i += 1\n",
    "                continue\n",
    "\n",
    "            # 开始读取数字\n",
    "            j = i\n",
    "            num, sign = 0, 1\n",
    "            if s[j] == '-':\n",
    "                sign = -1\n",
    "                j += 1\n",
    "            while j < len(s) and s[j].isdigit():\n",
    "                num = num * 10 + (ord(s[j]) - ord('0'))\n",
    "                j += 1\n",
    "            i = j\n",
    "            num = num*sign    \n",
    "            \n",
    "            # 建树: 栈顶元素就是父节点\n",
    "            node = TreeNode(num)\n",
    "            if stk:\n",
    "                parent = stk[-1]\n",
    "                if not parent.left:\n",
    "                    parent.left = node\n",
    "                else: parent.right = node\n",
    "            stk.append(node)\n",
    "        return stk[-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        n = len(s)\n",
    "        def dfs(i):\n",
    "            if i >= n:\n",
    "                return i, None\n",
    "            \n",
    "            j = i\n",
    "            while j < n:\n",
    "                if s[j] in ('(', ')'):\n",
    "                    break\n",
    "                j += 1\n",
    "\n",
    "            root = TreeNode(val=int(s[i:j]))\n",
    "            i = j\n",
    "\n",
    "            if i == n or s[i] == ')':\n",
    "                return i + 1, root \n",
    "            \n",
    "            i, left = dfs(i+1)\n",
    "            root.left = left\n",
    "\n",
    "            if i >= n or s[i] != '(':\n",
    "                return i+1, root\n",
    "            \n",
    "            i, right = dfs(i+1)\n",
    "            root.right = right\n",
    "\n",
    "            return i + 1, root\n",
    "\n",
    "\n",
    "        return dfs(0)[1]\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        tmp = []\n",
    "        index = 0\n",
    "        n = len(s)\n",
    "        # 切割成为( ) 以及数字的数组\n",
    "        while index < n:\n",
    "            if s[index] == '(':\n",
    "                tmp.append('(')\n",
    "                index += 1\n",
    "            elif s[index] == ')':\n",
    "                tmp.append(')')\n",
    "                index += 1\n",
    "            else:\n",
    "                start = index\n",
    "                while index < n and s[index] != '(' and s[index] != ')':\n",
    "                    index += 1\n",
    "                tmp.append(s[start:index])\n",
    "\n",
    "        st = []\n",
    "\n",
    "        for c in tmp:\n",
    "            # 遇到数字就建立节点 入栈\n",
    "            if c and c[-1].isdigit():\n",
    "                st.append(TreeNode(int(c)))\n",
    "            elif c == ')':\n",
    "                # 遇到右边的括号 就出栈 出栈的时候考虑下父亲节点的左右儿子 如果左节点不存在就挂在左边\n",
    "                cur = st.pop()\n",
    "                if st[-1].left:\n",
    "                    st[-1].right = cur\n",
    "                else:\n",
    "                    st[-1].left = cur\n",
    "        return st.pop()"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> TreeNode:\n",
    "        if len(s) == 0:\n",
    "            return None\n",
    "        if '(' not in s:\n",
    "            return TreeNode(int(s[:]))\n",
    "        pos = s.index('(')\n",
    "        root = TreeNode(int(s[0: pos]))\n",
    "        start = pos                    #（start是某棵子树，区间的起始index，第一个左括号）\n",
    "        cnt = 0\n",
    "        for i in range(pos, len(s)):\n",
    "            if s[i] == '(':     cnt += 1\n",
    "            elif s[i] == ')':   cnt -= 1\n",
    "\n",
    "            if cnt == 0 and start == pos:       #左子的部分\n",
    "                root.left = self.str2tree(s[start+1: i])\n",
    "                start = i + 1\n",
    "            elif cnt == 0 and start != pos:    #右子的部分 这个地方必须用 elif!!!!!!\n",
    "                root.right = self.str2tree(s[start + 1 : i])\n",
    "\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        if \"(\" not in s:\n",
    "            return TreeNode(int(s))\n",
    "\n",
    "        # 寻找左子树与右子树的字符串范围\n",
    "        n = len(s)\n",
    "        left = right = 0\n",
    "        start = end = -1\n",
    "        for i in range(n):\n",
    "            if s[i] == \"(\":\n",
    "                if start == -1:\n",
    "                    start = i\n",
    "                left += 1\n",
    "            elif s[i] == \")\":\n",
    "                right += 1\n",
    "            if left == right and left:\n",
    "                end = i\n",
    "                break\n",
    "        \n",
    "        # 注意索引边界\n",
    "        root = TreeNode(int(s[:start]))\n",
    "        root.left = self.str2tree(s[start + 1:end])\n",
    "        root.right = self.str2tree(s[end + 2:-1])\n",
    "        return root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        s = '('+s+')'\n",
    "        def getNum(i):\n",
    "            for ind in range(i, len(s)):\n",
    "                if s[ind] in ['(', ')']:\n",
    "                    print(s[i:ind])\n",
    "                    return int(s[i:ind]), ind\n",
    "\n",
    "        if s == '()':\n",
    "            return None\n",
    "\n",
    "        n, i = getNum(1)\n",
    "        root = TreeNode(n)\n",
    "        stack = deque([root])\n",
    "        ind = i\n",
    "        while ind < len(s):\n",
    "            if s[ind] == '(':\n",
    "                ind += 1\n",
    "                n, i = getNum(ind)\n",
    "                new_node = TreeNode(n)\n",
    "                ind = i\n",
    "                if not stack[-1].left:\n",
    "                    stack[-1].left = new_node    \n",
    "                else:\n",
    "                    stack[-1].right = new_node\n",
    "                stack.append(new_node)\n",
    "            elif s[ind] == ')':\n",
    "                stack.pop()\n",
    "                ind += 1\n",
    "        return root\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if s is None or len(s) == 0:\n",
    "            return  None\n",
    "\n",
    "        stack = []\n",
    "\n",
    "        for c in s:\n",
    "            if c != ')':\n",
    "                stack.append(c)\n",
    "            else:\n",
    "                cur = stack.pop()\n",
    "                if isinstance(cur,str):\n",
    "                    while len(stack) > 0:\n",
    "                        stackEnd = stack.pop()\n",
    "                        if stackEnd != '(':\n",
    "                            cur += stackEnd\n",
    "                        else:\n",
    "                            break\n",
    "                    curNode = TreeNode(val=int(cur[::-1]))\n",
    "                    stack.append(curNode)\n",
    "                else:\n",
    "                    curList = [cur]\n",
    "                    cur = \"\"\n",
    "                    while len(stack) > 0:\n",
    "                        stackEnd = stack.pop()\n",
    "                        if stackEnd == '(':\n",
    "                            break\n",
    "                        if isinstance(stackEnd,TreeNode):\n",
    "                            curList.append(stackEnd)\n",
    "                        else:\n",
    "                            cur += stackEnd\n",
    "                    curRoot = TreeNode(val=int(cur[::-1]))\n",
    "                    if len(curList) == 1:\n",
    "                        curRoot.left = curList.pop()\n",
    "                    elif len(curList) == 2:\n",
    "                        curRoot.left = curList.pop()\n",
    "                        curRoot.right = curList.pop()\n",
    "\n",
    "                    stack.append(curRoot)\n",
    "        curList = []\n",
    "        cur = \"\"\n",
    "        curRoot = None\n",
    "        while len(stack) > 0:\n",
    "            stackEnd = stack.pop()\n",
    "            if stackEnd == '(':\n",
    "                break\n",
    "            if isinstance(stackEnd, TreeNode):\n",
    "                curList.append(stackEnd)\n",
    "            else:\n",
    "                cur += stackEnd\n",
    "        curRoot = TreeNode(val=int(cur[::-1]))\n",
    "        if len(curList) == 1:\n",
    "            curRoot.left = curList.pop()\n",
    "        elif len(curList) == 2:\n",
    "            curRoot.left = curList.pop()\n",
    "            curRoot.right = curList.pop()\n",
    "        return curRoot"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        if not s:\n",
    "            return None\n",
    "        tmp = []\n",
    "        index = 0\n",
    "        n = len(s)\n",
    "        while index < n:\n",
    "            if s[index] == '(':\n",
    "                tmp.append('(')\n",
    "                index += 1\n",
    "            elif s[index] == ')':\n",
    "                tmp.append(')')\n",
    "                index += 1\n",
    "            else:\n",
    "                start = index\n",
    "                while index < n and s[index] != '(' and s[index] != ')':\n",
    "                    index += 1\n",
    "                tmp.append(s[start:index])\n",
    "\n",
    "        st = []\n",
    "\n",
    "        for c in tmp:\n",
    "            if c and c[-1].isdigit():\n",
    "                st.append(TreeNode(int(c)))\n",
    "            elif c == ')':\n",
    "                cur = st.pop()\n",
    "                if st[-1].left:\n",
    "                    st[-1].right = cur\n",
    "                else:\n",
    "                    st[-1].left = cur\n",
    "        return st[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "'''\n",
    "将包含括号的字符串转换为嵌套的多维数组，以便后续处理\n",
    "'''\n",
    "def Parentheses2Array(s: str, left_mark=\"(\", right_mark=\")\")->list[str]:\n",
    "    if not s: return []\n",
    "    def f(left, right):\n",
    "        if s.find(left_mark, left, right) == -1: return [s[left:right]]\n",
    "        l = s.find(left_mark, left, right)\n",
    "        r = s.rfind(right_mark, left, right)\n",
    "        rnt, last, cnt = [], l, 0\n",
    "        if s[left:l]: rnt.append(s[left:l])\n",
    "        for i in range(l, r+1):\n",
    "            if s[i] == left_mark: cnt += 1\n",
    "            elif s[i] == right_mark: cnt -= 1\n",
    "            if cnt == 0: \n",
    "                t, last = f(last+1, i), i+1\n",
    "                if t: rnt.append(t)\n",
    "        if s[r+1:right]: rnt.append(s[r+1:right])\n",
    "        return rnt\n",
    "    return f(0, len(s))\n",
    "\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        lst = Parentheses2Array(s)\n",
    "        def f(x):\n",
    "            if not x: return None\n",
    "            rnt = TreeNode(val=int(x[0]))\n",
    "            if len(x) >= 2: rnt.left = f(x[1])\n",
    "            if len(x) == 3: rnt.right = f(x[2])\n",
    "            return rnt\n",
    "        return f(lst)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "'''\n",
    "将包含括号的字符串转换为嵌套的多维数组，以便后续处理\n",
    "'''\n",
    "def Parentheses2Array(s: str, left_mark=\"(\", right_mark=\")\")->list[str]:\n",
    "    if not s: return []\n",
    "    if s.find(left_mark) == -1: return [s]\n",
    "    rnt, s0, cnt = [], \"\", 0\n",
    "    l, r = s.find(left_mark), s.rfind(right_mark)\n",
    "    if s[:l]: rnt.append(s[:l])\n",
    "    for x in s[l:r+1]:\n",
    "        s0 += x\n",
    "        if x == left_mark: cnt += 1\n",
    "        elif x == right_mark: cnt -= 1\n",
    "        if cnt == 0: \n",
    "            t = Parentheses2Array(s0[1:-1])\n",
    "            if t: rnt.append(t)\n",
    "            s0 = \"\"\n",
    "    if s[r+1:]: rnt.append(s[r+1:])\n",
    "    return rnt\n",
    "\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        lst = Parentheses2Array(s)\n",
    "        def f(x):\n",
    "            if not x: return None\n",
    "            rnt = TreeNode(val=int(x[0]))\n",
    "            if len(x) >= 2: rnt.left = f(x[1])\n",
    "            if len(x) == 3: rnt.right = f(x[2])\n",
    "            return rnt\n",
    "        return f(lst)\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, val=0, left=None, right=None):\n",
    "#         self.val = val\n",
    "#         self.left = left\n",
    "#         self.right = right\n",
    "class Solution:\n",
    "    def str2tree(self, s: str) -> Optional[TreeNode]:\n",
    "        i=0\n",
    "        if s=='':return None\n",
    "        news=[]\n",
    "        temp=\"\"\n",
    "        for item in s:\n",
    "            if item =='(' or item ==')':\n",
    "                news.append(temp)\n",
    "                news.append(item)\n",
    "                temp=''\n",
    "            else:\n",
    "                temp+=item\n",
    "        if temp!='':news.append(temp)\n",
    "        s=news\n",
    "        def pre_order():\n",
    "            nonlocal i\n",
    "            root=TreeNode(val=int(s[i]))\n",
    "            i+=1\n",
    "            count=0\n",
    "            judge=0\n",
    "            while i<len(s) and not (count==0 and s[i]==')'):\n",
    "                if s[i]=='(':\n",
    "                    if judge==0:\n",
    "                        count+=1\n",
    "                        i+=1\n",
    "                        root.left=pre_order()\n",
    "                        judge=1\n",
    "                    else:\n",
    "                        count+=1\n",
    "                        i+=1\n",
    "                        root.right=pre_order()\n",
    "                elif s[i]==')':\n",
    "                    count-=1\n",
    "                    i+=1\n",
    "                else:\n",
    "                    i+=1\n",
    "            return root\n",
    "        \n",
    "        return pre_order()"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
